class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def create_tree(nums):

    def dfs(left,right):
        if left > right:
            return None
        mid = (left+right)//2
        root = TreeNode(nums[mid])

        root.left = dfs(left,mid-1)
        root.right = dfs(mid+1,right)

        return root
    return dfs(0,len(nums)-1)

def preorder(root):
    if not root:
        return
    print(root.val)
    preorder(root.left)
    preorder(root.right)

def inorder(root):
    if not root:
        return None
    inorder(root.left)
    print(root.val)
    inorder(root.right)

def inorder_stack(root):
    stack =[]
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        print(root.val)
        root = root.right
def levelOrder(root):
    if root ==None:
        return None
    res = []
    q = []
    q.append(root)
    while q:
        size = len(q)
        tmp =[]
        for i in range(size):
            t = q.pop(0)
            tmp.append(t.val)
            if t.left:
                q.append(t.left)
            if t.right:
                q.append(t.right)
        res.append(tmp)
    return res

def isValidVST(root):
    def dfs(root,lower,upper):
        if root is None:
            return True
        if root.val <= lower or root.val >= upper:
            return False

        if dfs(root.left,lower,root.val) is False:
            return False
        if dfs(root.right,root.val,upper) is False:
            return False
        return True
    return dfs(root,-1e15,1e15)

def isValiBST2(root):
    pre_val =-1e15
    if root is None:
        return True
    if isValiBST2(root.left) is True:
        if root.val > pre_val:
            pre_val = root.val
        else:
            return False
        return isValiBST2(root.right)
    return False

if __name__=="__main__":
    nums = [1,2,3,4,5,6,7,8,9]
    root = create_tree(nums)
    c= isValiBST2(root)
    print(c)
